/*
 * @Author: 缄默
 * @Date: 2021-11-11 20:15:12
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 20:41:18
 */

//二叉树结点间的最大距离问题
//二叉树dp问题解题思路要有，简单来说 就是如何实现递归

#include <iostream>
#include <vector>
#include "../../DataStructure/tree.hpp"


using namespace std;

struct returnType {
    int max;
    int height;
    returnType(int x1, int x2) : max(x1), height(x2) { }
};


int getMaxInstance(TreeNode* head);
returnType* getMax(TreeNode* head);

int main() {
    vector<int> preOrder({4, 2, 1, 0, 3, 6, 5, 7});
    vector<int> inOrder({0, 1, 2, 3, 4, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    cout << getMaxInstance(head) << endl;
    return 0;
}

int getMaxInstance(TreeNode* head) {
    return getMax(head)->max;
}

returnType* getMax(TreeNode* head) {
    if (head == nullptr) return new returnType(0, 0);
    returnType* left = getMax(head->left);
    returnType* right = getMax(head->right);
    int max = left->height + right->height - 1;
    max = max < left->max ? left->max : max;
    max = max < right->max ? right->max : max;
    int height = (left->height < right->height ? right->height : left->height) + 1;
    return new returnType(max, height);
}